/*
 * Copyright (c) 2011-2012 Alexander Dubu
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *
 * o  Redistributions of source code must retain the above copyright notice,
 *    this list of conditions and the following disclaimer.
 *
 * o  Redistributions in binary form must reproduce the above copyright notice,
 *    this list of conditions and the following disclaimer in the documentation
 *    and/or other materials provided with the distribution.
 *
 * o  Neither the name Axil nor the names of its contributors may be used to
 *    endorse or promote products derived from this software without specific
 *    prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 * POSSIBILITY OF SUCH DAMAGE.
 */
package axil.stdlib.numbers.type;

import axil.api.AxilObject;
import axil.api.AxilType;
import axil.api.Formatting;
import axil.api.Persona;

import java.math.BigDecimal;
import java.math.MathContext;
import java.math.RoundingMode;

import static axil.framework.Functions.*;


/**
 * An Axil object representing fractions.
 */
public class Fraction extends Num {
	public static final AxilType type = Fraction_Type.object;
	public static final Fraction zero = new Fraction(0, 1);

	private int numerator;
	private int denominator;


	public Fraction(int numerator, int denominator) {
        // reduce fraction to simplest terms
        int gcd = gcd(numerator, denominator);
        if(gcd != 0  && gcd != 1) {
            numerator = numerator / gcd;
            denominator = denominator / gcd;
        }

		if ((numerator < 0 && denominator < 0) || (numerator > 0 && denominator < 0)) {
            // ensure that any negative sign is held in the numerator and that double negatives result in a positive
            this.numerator = numerator * -1;
		    this.denominator = denominator * -1;
        } else {
            this.numerator = numerator;
            this.denominator = denominator;
        }
	}


	public static Fraction from(int n, int d) {
		return new Fraction(n, d);
	}


	public static Fraction from(int whole, int n, int d) {
		return new Fraction(n + (whole * d), d);
	}


	public static Fraction from(double value) {
        // Convert floating point representation to fractional representation using continued fraction expansion.
        // For all continued fractions whose convergence is less than 1,000 terms this will result in an exact
        // conversion, while all others will be truncated after 1,000 terms and approximated in order to prevent
        // overly long computation times.
        int aTerm; // a_0, a_1, ..., a_i, ..., a_19
        double[] p = new double[3]; // p_i, p_i-1, p_i-2
        double[] q = new double[3]; // q_i, q_i-1, q_i-2
        int i = 0; // counter

        // get the positive floating point representation of value (we will append the proper sign later)
        BigDecimal floater = new BigDecimal(Math.abs(value));

        // set floater to round off floating point miscalculations
        floater.setScale(15, BigDecimal.ROUND_HALF_EVEN);

        // initialize p_-1, p_-2, q_-1, and q_-2
        p[1] = 1;
        p[2] = 0;
        q[1] = 0;
        q[2] = 1;

        // calculate the terms of the continued fraction, rounding where appropriate, and compute the p and q terms
        while (i < 1000 && floater.doubleValue() != 0) {
            // Move this term from floater into the aTerm
            aTerm = (int) Math.floor(floater.doubleValue());
            floater = floater.subtract(BigDecimal.valueOf(aTerm));

            // Set floater equal to its inverse in order to determine the next term
            if(floater.doubleValue() != 0) {
                floater = BigDecimal.valueOf(1).divide(floater, 5, RoundingMode.HALF_EVEN);
            }

            // ensure that this iteration will not cause p[0] or q[0] to overflow
            if(p[1] != 0 && (Math.abs(aTerm) > Math.abs(Double.MAX_VALUE / p[1])) &&
                    q[1] != 0 && (Math.abs(aTerm) > Math.abs(Double.MAX_VALUE / q[1])))
            {
                throw abort("The floating point value is too large to represent as a " +
                        "meaningful fraction.", nv("value", value));
            }

            // calculate p_i = a_i * p_i-1 + p_i-2 and update p values
            p[0] = aTerm * p[1] + p[2];
            p[2] = p[1];
            p[1] = p[0];

            // calculate q_i = a_i * q_i-1 + q_i-2 and update q values
            q[0] = aTerm * q[1] + q[2];
            q[2] = q[1];
            q[1] = q[0];

            // if we already have the solution stop processing
            if (p[0] / q[0] == value) {
                floater = BigDecimal.valueOf(0);
            }

            i++;
        }

        // when this conversion happens, users are more than likely looking for easily readable fractions (those seeking
        // precision will likely keep things in decimal format), so if the terms of the fraction are both > 100,000
        // we will round with a precision of 6 digits before simplifying the fraction
        if (p[0] > 100000 && q[0] > 100000) {
            p[0] = BigDecimal.valueOf(p[0]).round(new MathContext(6, RoundingMode.HALF_EVEN)).intValue();
            q[0] = BigDecimal.valueOf(q[0]).round(new MathContext(6, RoundingMode.HALF_EVEN)).intValue();
        }

        if (p[0] > Integer.MAX_VALUE || q[0] > Integer.MAX_VALUE) {
            if (value > 0) {
                throw abort("The floating point value is too large to represent as a " +
                    "meaningful fraction.", nv("value", value));
            } else {
                throw abort("The floating point value is too small to represent as a " +
                        "meaningful fraction.", nv("value", value));
            }
        }

        // return a correctly signed fraction
        if (value > 0) {
            return new Fraction((int) p[0], (int) q[0]);
        } else {
            return new Fraction((int) p[0] * -1, (int) q[0]);
        }
	}


	public static Fraction from(Decimal value) {
        return from(value.fp());
	}


	/**
	 * Get the type metadata for this object. The type metadata contains
	 * information about the type itself, as an object.
	 */
	public AxilType type() {
		return type;
	}


	/**
	 * Tell the magnitude of this numeric value. This is used in all arithmetic
	 * computations to ensure like objects are used.
	 */
	public int kind() {
		return FRACTION;
	}


	/**
	 * Return the value of this object as an object of the indicated size. It
	 * can be safely assumed that the caller intended whatever side effects
	 * occur as part of the conversion are intentional.
	 */
	public Num as(int kind) {
		switch(kind) {
		case INT:
			return Int.from(numerator / denominator);
		case BIGINT:
			return BigInt.from(numerator / denominator);
		case FRACTION:
			return this;
		case FP:
			return FloatingPoint.from(fp());
		case DECIMAL:
			return new Decimal(BigDecimal.valueOf(numerator).divide(BigDecimal.valueOf(denominator)));
        case PERCENT:
            return new Percent(new Decimal(BigDecimal.valueOf(numerator).divide(BigDecimal.valueOf(denominator))));

		default:
			throw abort("Unrecognized kind", nv("kind", kind));
		}
	}


	/**
	 * Return the canonical representation of a zero value in this numeric
	 * type.
	 */
	public Num zero() {
		return zero;
	}


	private int gcd(int a, int b) {
		// Euclidean algorithm
		while (b != 0) {
			int t = b;
			b = a % b;
			a = t;
		}
		return a;
	}


	private int lcm(int a, int b) {
		return a * b / gcd(a, b);
	}


	/**
	 * Returns a hash code value for the object. All Axil values must provide a
	 * meaningful implementation of this function to enable themselves to be
	 * placed in a map or set.
	 */
	protected int hash() {
		return numerator + denominator;
	}


	/**
	 * Tell if this number has any significant fractional digits. For example,
	 * the number 3.1 would return true, but 3.0 would not.
	 */
	public boolean fractional() {
		return numerator % denominator > 0;
	}


	/**
	 * Get this value as an integer value, discarding any fractional component.
	 * For example, 12.65 returns the integer value 12. No rounding is performed,
	 * only truncation. If the value is greater than what can fit in a 64-bit
	 * integer, then an exception is thrown.
	 */
	public long whole() {
		BigDecimal num = BigDecimal.valueOf(numerator);
        BigDecimal denom = BigDecimal.valueOf(denominator);
        return num.divide(denom, 0, RoundingMode.DOWN).longValue();
	}


	/**
	 * Get the fractional portion of this numeric value as a floating point
	 * value. For example, 12.325 returns a value of 0.325. If there is no
	 * fractional portion, then 0.0 is returned.
	 */
	public double tenths() {
		BigDecimal num = BigDecimal.valueOf(numerator);
        BigDecimal denom = BigDecimal.valueOf(denominator);
        BigDecimal whole = num.divide(denom, 0, RoundingMode.DOWN);
        return num.divide(denom).subtract(whole).doubleValue();
	}


	/**
	 * Return a true value if this number is greater than zero. A value of zero
	 * returns a false value.
	 */
	public boolean positive() {
		return numerator > 0;
	}


	/**
	 * Tell if this object is equivalent to the given object. The object given
	 * is never null. The object given may be of any type of value object.  If
	 * the given object is not a suitable type for comparison, a
	 * ClassCastException may be thrown.
	 */
	public boolean eq(Fraction v) {
		int a = this.numerator * v.denominator;
		int b = this.denominator * v.numerator;
		return a == b;
	}


	/**
	 * Tell if this object is equivalent to the given object. The object given
	 * is never null. The object given may be of any type of value object.  If
	 * the given object is not a suitable type for comparison, a
	 * ClassCastException may be thrown.
	 */
	public boolean equalTo(AxilObject object) {
		if (object instanceof Num) {
			Num n = (Num)object;
			switch(n.kind()) {
			case INT:
				if (fractional()) {
					return false;
				}
				return ((Int)n).value() == (numerator / denominator);

			case BIGINT:
				if (fractional()) {
					return false;
				}
				return as(BIGINT).equalTo(n);

			case PERCENT:
				return fp() == n.fp();
			case FRACTION:
				return eq((Fraction)n);
			case FP:
				return fp() == n.fp();
			case DECIMAL:
				return as(DECIMAL).equalTo(n);
			case UNITIZED:
				return equalTo(mag(n));

			default:
				throw unreachable();
			}
		}
		return false;
	}


	/**
	 * Compares this object with the specified object for order. If the given
	 * object is not a suitable type for comparison, a ClassCastException may
	 * be thrown.
	 *
	 * @param object
	 * 	The object to compare against. The given object cannot be null but may
	 * 	be any Axil object.
	 *
	 * @return
	 * 	Returns a negative integer, zero, or a positive integer as this object
	 * 	is less than, equal to, or greater than the specified object.
	 */
	public int comparedTo(AxilObject object) {
		Num n = num(object);
		double d = this.fp() - n.fp();
		return d < 0.0D ? -1 : d > 0.0D ? 1 : 0;
	}


	/**
	 * Add the given number of this number. This method can safely assume that
	 * the given value is not null and is of the exact same type as this value.
	 */
	public AxilObject add(AxilObject n) {
        if (n instanceof Fraction) {
            Fraction b = (Fraction)n;
            int lcm = lcm(denominator, b.denominator);
            int an = (lcm / denominator) * numerator;
            int bn = (lcm / b.denominator) * b.numerator;
            return from(an + bn, lcm);
        } else {
            Num v = num(n);
            int kind = upcast(this, v);
            return as(kind).add(v.as(kind));
        }
	}


	/**
	 * Subtract the given number from this number. This method can safely assume
	 * that the given value is not null and is of the exact same type as this
	 * value.
	 */
	public AxilObject subtract(AxilObject n) {
        if (n instanceof Fraction) {
            Fraction b = (Fraction)n;
            int lcm = lcm(denominator, b.denominator);
            int an = (lcm / denominator) * numerator;
            int bn = (lcm / b.denominator) * numerator;
            return from(an - bn, lcm);
        } else {
            Num v = num(n);
            int kind = upcast(this, v);
            return as(kind).subtract(v.as(kind));
        }
	}


	/**
	 * Multiply the given number by this number. This method can safely assume
	 * that the given value is not null and is of the exact same type as this
	 * value.
	 */
	public Num multiply(Num n) {
        if (n instanceof Fraction) {
            Fraction b = (Fraction)n;
            return from(numerator * b.numerator, denominator * b.denominator);
        } else {
            Num v = num(n);
            int kind = upcast(this, v);
            return as(kind).multiply(v.as(kind));
        }
	}


	/**
	 * Divide this number by the given number. This method can safely assume
	 * that the given value is not null and is of the exact same type as this
	 * value.
	 */
	public Num divide(Num n) {
        if (n instanceof Fraction) {
            Fraction b = (Fraction)n;
            return from(numerator * b.denominator, denominator * b.numerator);
        } else {
            Num v = num(n);
            int kind = upcast(this, v);
            return as(kind).divide(v.as(kind));
        }
	}


	/**
	 * Round this value according to the rules of the given rounding mode and
	 * to the given number of significant fractional digits. A value of zero
	 * rounds this to a whole number.
	 */
	public Num round(RoundingMode mode, int digits) {
		return from((Decimal)(as(DECIMAL).round(mode, digits)));
	}


	/**
	 * Format this object in a locale-friendly manner. The string returned is
	 * a localized representation of this object using the locale and timezone
	 * associated with this persona. The formatting given is never null and
	 * matches formatting suitable for this type.
	 */
	public String format(Persona persona, Formatting formatting) {
		return Integer.toString(numerator) + '/' + denominator;
	}


	/**
	 * Return a floating point representation of this object. If this object has
	 * no meaningful numeric representation, then an exception is thrown.
	 *
	 * @return
	 * 	Returns this object as a floating point value.
	 */
	public final double fp() {
		return (double)numerator / (double)denominator;
	}


	/**
	 * Returns a hash code value for the object. This method is supported for
	 * the benefit of hash tables and such. By default, numbers return the
	 * nearest integer representation of this object.
	 */
	public int hashCode() {
		return (int)(fp() * 10000.0D);
	}


	/**
	 * Return the host application (or built-in Java) object that most closely
	 * matches this value object. Return returned value is never null unless
	 * this value object represents the special 'nil' object.
	 */
	public Object intrinsic() {
		return this;
	}


	/**
	 * Return a string representation of this object. The string returned is
	 * never null.
	 */
	public String toString() {
		return Integer.toString(numerator) + '/' + denominator;
	}
}
